package leetcode_jz_offer.day15_huisuAndBintree;

/**
 * @author 美女
 * @date 2022/07/30 16:50
 **/
public class Num54_二叉树第k大结点 {
    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    int res;//结果
    int k;//第k大结点
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        //求二叉树第k大结点
        dfs(root);
        return res;
    }
    //中序遍历的倒叙：中序遍历得到一个升序值，她的倒叙就是一个降序，第k大就变为求第k个结点
    //中序：左根右；倒序后：右根左
    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        dfs(root.right);
        //处理结点
        if(k==0){
            return;
        }
        if(--k==0){//k不断减减到0时，得到的那个结点就是第k大结点，拿到节点值直接返回即可
            res=root.val;
        }
        dfs(root.left);
    }
}
